#include <bits/stdc++.h>
#define N 100010

using namespace std;

namespace AC{

struct Node{
    int son[26];
    int ans;
    int fail;
    int du;
    int idx;
    void init()
    {
        memset(son,0,sizeof(son));
        ans = fail = idx = 0;
    }
}tr[N];

int tot;//node num
int ans[N],pidx;

void init()
{
    tot = pidx = 0;
    tr[0].init();
}

void insert(char s[],int& idx)
{
    int u = 0;
    for(int i = 0;s[i];++i)
    {
        int& son = tr[u].son[s[i]-'a'];
        if(!son)
        {
            son = ++tot;
            tr[son].init();
        }
        u = son;
    }
    if(!tr[u].idx)
    {
        tr[u].idx = ++pidx;
    }
    idx = tr[u].idx;
}

void build()
{
    queue<int> q;
    for(int i = 0;i<26;++i)
    {
        if(tr[0].son[i]) 
        {
            q.push(tr[0].son[i]);
        }
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = 0;i<26;++i)
        {
            if(tr[u].son[i])
            {
            tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
            tr[tr[tr[u].fail].son[i]].du++;
            q.push(tr[u].son[i]);
            }
            else
            {
                tr[u].son[i] = tr[tr[u].fail].son[i];
            }
        }

    }
}

}
